\section{Подсчет бит}
\label{POPCNT}

Инструкция \INS{POPCNT} (\IT{population count}) служит для подсчета бит во входном значении (\ac{AKA} расстояние Хэмминга).

В качестве побочного эффекта, инструкция \INS{POPCNT} (или операция) может использоваться, чтобы узнать,
имеет ли значение вид $2^n$.
Так как числа $2^n$ всегда имеют только один выставленный бит, результат \INS{POPCNT} всегда будет просто 1.

\myindex{base64scanner}
Например, я однажды написал сканер для поиска base64-строк в бинарных файлах\footnote{\url{https://github.com/dennis714/base64scanner}}.
И есть много мусора и ложных срабатываний, так что я добавил опцию для фильтрования блоков данных, размер которых $2^n$ байт
(т.е., 256 байт, 512, 1024, итд.).
Размер блока проверяется так:

\begin{lstlisting}[style=customc]
if (popcnt(size)==1)
	// OK
...
\end{lstlisting}

Инструкция также известна как \q{инструкция \ac{NSA}} из-за слухов:

\begin{framed}
\begin{quotation}
  This branch of cryptography is fast-paced and very politically charged.
  Most designs are secret; a majority of military encryptions systems in use today are 
  based on LFSRs. 
  In fact, most Cray computers (Cray 1, Cray X-MP, Cray Y-MP) have a rather curious 
  instruction generally known as “population count.” It counts the 1 bits in a register 
  and can be used both to efficiently calculate the Hamming distance between two binary 
  words and to implement a vectorized version of a LFSR. I’ve heard this called the canonical 
  NSA instruction, demanded by almost all computer contracts.
\end{quotation}
\end{framed}
\InSqBrackets{\Schneier{}}

